package com.chj.jz.dp.class06;

public class Code08_OnesAndZeroes {
	/**
	 * @param strs:
	 *            an array with strings include only 0 and 1
	 * @param m:
	 *            An integer
	 * @param n:
	 *            An integer
	 * @return: find the maximum number of strings
	 */
	public static int findMaxForm(String[] A, int m, int n) {
		if (A.length == 0) {
			return 0;
		}

		int T = A.length;
		// int[] cnt0 = new int[T];
		// int[] cnt1 = new int[T];
		int i, j, k, a0, a1;
		// for (i = 0; i < T; ++i) {
		// cnt0[i] = cnt1[i] = 0;
		// char[] s = A[i].toCharArray();
		// for (j = 0; j < s.length; ++j) {
		// if (s[j] == '0') {
		// ++cnt0[i];
		// }
		// else {
		// ++cnt1[i];
		// }
		// }
		// }

		int[][][] f = new int[T + 1][m + 1][n + 1];
		for (j = 0; j <= m; j++) {
			for (k = 0; k <= n; k++) {
				f[0][j][k] = 0;
			}
		}

		// int res = 0;
		for (i = 1; i <= T; ++i) {

			a0 = a1 = 0;
			for (j = 0; j < A[i - 1].length(); j++) {
				if (A[i - 1].charAt(j) == '0') {
					a0++;
				} else {
					a1++;
				}
			}

			for (j = 0; j <= m; ++j) {
				for (k = 0; k <= n; ++k) {
					// do not take A[i - 1]
					f[i][j][k] = f[i - 1][j][k];

					// take A[i - 1]
					if (j >= a0 && k >= a1) {
						f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j - a0][k - a1] + 1);
					}
				}
			}
		}

		return f[T][m][n];
	}
	
	 public static void main(String[] args) {
			{
				String[] arrK = new String[] {"10", "0001", "111001", "1", "0"};
				int m = 5;
				int n = 3;
				System.out.println(findMaxForm(arrK, m, n));
			}
			{
				String[] arrK = new String[] {"10", "0001", "111001", "1", "0"};
				int m = 7;
				int n = 7;
				System.out.println(findMaxForm(arrK, m, n));
			}
	    }
}
